package com.gitee.ty850454.leetcode224;

/**
 * 基本计算器
 *
 * 实现一个基本的计算器来计算一个简单的字符串表达式 s 的值。
 *
 * 示例 1：
 * 输入：s = "1 + 1"
 * 输出：2
 *
 * 示例 2：
 * 输入：s = " 2-1 + 2 "
 * 输出：3
 *
 * 示例 3：
 * 输入：s = "(1+(4+5+2)-3)+(6+8)"
 * 输出：23
 *
 * 提示：
 * 1 <= s.length <= 3 * 105
 * s 由数字、'+'、'-'、'('、')'、和 ' ' 组成
 * s 表示一个有效的表达式
 *
 * 思考：
 * 这题看似有一堆括号，存在优先级问题，但是因为只有加减法，所以其实还是从左向右计算，如果括号外是加法，无视括号，如果括号外是减法，括号内算法结果取反
 *
 * @author xy
 */
public class Leetcode224_2 {

    public static void main(String[] args) {
        Leetcode224_2 instance = new Leetcode224_2();
        System.out.println(instance.calculate("1 + 1"));
        System.out.println(instance.calculate(" 2-1 + 2"));
        System.out.println(instance.calculate("12-1+22"));
        System.out.println(instance.calculate("2-(1+2)-(2-2)"));
        System.out.println(instance.calculate("(1+(4+5+2)-3)+(6+8)"));
        System.out.println(instance.calculate("1+2-(3-(2-3))"));
    }

    public int calculate(String s) {
        char[] chars = s.toCharArray();

        int sign = 1;

        int[] stack = new int[chars.length];
        int topIndex = -1;
        stack[++topIndex] = sign;

        int result = 0;

        for (int i = 0; i < chars.length;) {
            char aChar = chars[i];
            if (aChar == ' ') {
                i++;
            } else if (aChar == '+') {
                sign = stack[topIndex];
                i++;
            } else if (aChar == '-') {
                sign = -stack[topIndex];
                i++;
            } else if (aChar == '(') {
                stack[++topIndex] = sign;
                i++;
            } else if (aChar == ')') {
                topIndex--;
                i++;
            } else {
                // 取数字
                int num = aChar - '0';
                while (++i < chars.length && Character.isDigit(aChar = chars[i])) {
                    num = num * 10 + aChar - '0';
                }
                result += sign * num;
            }
        }
        return result;
    }
}
